<?php


namespace XiaoGuai\DataStructure\Forest\ChildSiblingTree;


use XiaoGuai\DataStructure\Forest\ChildSiblingTree\ChildSiblingTreeNode as Node;

/**
 * 孩子兄弟表示法, 树的二叉链表表示法
 * Class ChildSiblingForest
 * @package XiaoGuai\DataStructure\Forest\ChildSiblingTree
 */
class ChildSiblingForest
{

    /**
     * @var null|Node
     */
    protected $tree = null;

    public function __construct()
    {
        $this->tree = null;
    }

    // 用二叉树的先序遍历来构造孩子兄弟表示法
    public function create($orders = [])
    {
        $this->tree = $this->preOrderCreate($orders);
        return $this->tree;
    }

    public function preOrderCreate($orders = [])
    {
        if (empty($orders)) {
            return null;
        }

        // 判断结点是否为空
        $data = array_shift($orders);
        if (is_null($data)) {
            return null;
        }

        $node = new Node();
        $node->data = $data;

        $node->firstChild = $this->preOrderCreate(array_shift($orders));
        $node->sibling = $this->preOrderCreate(array_shift($orders));

        return $node;
    }

}